package dp.practice4;

import java.util.Arrays;

public class Main2 {
    public static void main(String[] args) {
        int[] moneys = new int[]{9, 7, 3, 10, 1, 5, 2};
        System.out.println(Arrays.toString(moneys));
        System.out.println(rob(moneys));
    }

    public static int rob(int[] moneys, int low, int high) {
        int include = 0, exclude = 0;
        //该算法保证首间房子一定被打劫
        for (int i = low; i <= high; i++) {
            int preExclude = exclude;
            exclude = Math.max(exclude, include);
            include = preExclude + moneys[i];
        }
        return Math.max(exclude, include);
    }

    public static int rob(int[] moneys) {
        if (moneys.length == 1)
            return moneys[0];
        return Math.max(rob(moneys, 0, moneys.length - 2), rob(moneys, 1, moneys.length - 1));
    }
}
